The advent of anti-retroviral therapy (ART) for people living with HIV/AIDS (PLWHA) substantially improved life expectancy but, now, PLWHA who smoke lose more life-years due to tobacco use than they do to their HIV infection. Unfortunately, the rate of smoking among PLWHA in the US is about 40%. The limited tobacco use treatment research with PLWHA indicates that behavioral treatments and medications (nicotine patch and varenicline) yield moderate effects on cessation, with quit rates that are considerably lower than they are for the general population. Thus, there is a critical need to identify novel ways to optimize tobacco cessation treatment for smokers with HIV. Two factors are highly predictive of cessation outcomes with pharmacotherapy, in the general population and among PLWHA. First, a smoker's rate of nicotine metabolism, characterized by the nicotine metabolite ratio (NMR, a marker of CYP2A6 gene variants), predicts cessation both for varenicline and nicotine patch. Our studies with general population and HIV-infected smokers show that personalizing the choice of medications for smokers using the NMR can increase efficacy and reduce toxicities, an approach highlighted by the NCI (https://www.cancer.gov/about-nci/budget/plan/public-health). Second, adherence to smoking cessation medications, in the general population and among PLWHA, rarely exceeds 60% and non-adherence lowers cessation rates 2-3 fold. We developed the Managed Problem Solving (MAPS) intervention which is endorsed by the CDC (https://www.cdc.gov/hiv/research/interventionresearch/compendium/ma/index.html) as an evidence-based intervention for medication adherence among PLWHA. Thus, the application's premise is that incorporating intervention components to tailor tobacco use medications (varenicline or patch) with the NMR and increase adherence to the medication using MAPS will optimize tobacco treatments for PLWHA. To test this premise, we will conduct a rigorous multi-site randomized clinical trial with 488 HIV+ smokers to evaluate NMR-tailored treatment and MAPS as optimization strategies for tobacco dependence treatment for PLWHA. We will use a factorial design to examine: 1) The effects of the NMR-tailored and/or MAPS interventions on end- of-treatment (EOT) and 6-month smoking cessation rates (primary aim); 2) Mediators of the NMR-tailored and MAPS interventions (secondary aim); and 3) Moderators of the NMR-tailored and MAPS interventions (exploratory aim). Our overall approach is consistent with the Multiphase Optimization Strategy which has gained prominence for guiding the evaluation of interventions for enhancing tobacco use treatment effectiveness. Addressing these aims will determine: the use of adherence and pharmacogenetic optimization of smoking cessation treatment for PLWHA, the mechanisms that underlie the effects of these optimization strategies on cessation outcomes, and the variation in the effects of these optimization strategies across sub-groups of PLWHA. In the end, this trial will help understand if getting the right medication to the right person and helping to make sure they sufficiently use that medication optimizes tobacco cessation treatment for this population.